\rsec{HITS}

O HITS foi objeto de estudo secundário neste trabalho. Como queríamos fazer um
estudo comparativo entre os mecanismos de busca baseados em popularidade e
referência entre páginas, estudamos esse método por também ser importante nesse
contexto.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{História}

O método HITS, acrônimo para \textit{Hypertext Induced Topic Search}, foi
concebido por Jon Kleinberg em 1998, durante o mesmo tempo em que Page e Brin
estavam trabalhando no \textit{PageRank}. O HITS é usado em um buscador web
chamado Teoma (\href{http://www.teoma.com/}{\texttt{www.teoma.com}}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Método}

Podemos perceber uma mudança para o \textit{PageRank} logo de início, ao saber
que o HITS é dependente dos termos da busca realizada, enquanto o
\textit{PageRank} não. O \textit{PageRank} atribui apenas um valor para cada
página, enquanto o HITS atribui dois. Estes valores são associados às qualidades
\textit{authority} e \textit{hub}. Uma página \textit{authority} é uma página
muito referenciada, e uma página \textit{hub} é uma página com muitas
referências. A ideia central do método diz que: ``boas \textit{authorities} são
referenciadas por bons \textit{hubs}, e bons \textit{hubs} referenciam boas
\textit{authorities}''.

Com isso, podemos dizer que cada página $i$ tem então um valor
\textit{authority} $x_i$ e um valor \textit{hub} $y_i$. Sendo $E$ o conjunto de
todos os \textit{links} do grafo da web e que $e_{ij}$ represente a referência
contida na página $i$ para a página $j$, a partir de um valor inicial
$x^{(0)}_i$ e $y^{(0)}_i$, o método HITS itera estes valores calculando:

$$
x^{(k)}_i = \sum_{j:e_{ji} \in E} y^{(k-1)}_j\;\;
\mbox{ e }\;\;
y^{(k)}_i = \sum_{j:e_{ij} \in E} x^{(k)}_j\;\;
\mbox{ para }k = 1, 2, 3,...
$$

Estas equações podem ser escritas na forma de multiplicação matriz-vetor,
utilizando a matriz $L$ da seção \ref{sec:webgraph}, que modela o grafo da web.

$$
x^{(k)} = L'y^{(k-1)}\;\;
\mbox{ e }\;\;
y^{(k)} = Lx^{(k)}
$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Algoritmo inicial}

As fórmulas anteriores nos levam a um algoritmo iterativo para o cálculo dos
vetores \textit{authority} e \textit{hub}.

\newpage

\texttt{
  \begin{algorithmic}
  \STATE $y^{(0)} \gets e$
  \WHILE {nao convergiu}
    \STATE $x^{(k)} \gets L'y^{(k-1)}$
    \STATE $y^{(k)} \gets Lx^{(k)}$
    \STATE $k \gets k + 1$
  \ENDWHILE
  \STATE Normalize $x^{(k)}$ e $y^{(k)}$
  \end{algorithmic}
}
Podemos perceber que as duas atribuições dentro do laço do algoritmo podem ser
substituídas por:
\begin{center}
$x^{(k)} = L'Lx^{(k-1)}$\\
$y^{(k)} = LL'y^{(k-1)}$
\end{center}

Estas duas novas equações definem o método da potência iterativo para calcular
o autovetor associado ao autovalor dominante das matrizes $L'L$ e $LL'$.
Elas são similares à convergência utilizada no \textit{PageRank}, utilizando
as duas matrizes citadas acima no lugar da \textit{Google matrix} $G$.
Como a matriz $L'L$ define os valores \textit{authority}, ela é chamada
\textit{authority matrix}, a matriz $LL'$ define os valores \textit{hub}, sendo
chamada \textit{hub matrix}. Ambas as matrizes são \textit{simétricas} e
\textit{semi-definidas positivas}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Implementação}

Originalmente, a implementação do HITS consistiria em dois passos:
\begin{itemize}
	\item Gerar grafo de vizinhança.\\\\
	A ideia básica consiste em pegar as páginas que contém os termos de busca e
	montar um	grafo $N$ no qual aparecem estas páginas e seus vizinhos. Claramente
	este grafo é menor que o grafo da web.
	\item Calcular os valores ``authority'' e ``hub''.\\\\
	Consistiria em utilizar um método da potência para calcular o vetor $x$ como sendo:
	$x'_{(k+1)} = x'_{k}N'N$ e após a convergência, ter $y' = x'N'$. (Aqui, N é a
	matriz de adjacência do grafo de vizinhança do item anterior).
\end{itemize}

No entanto, o algoritmo implementado foi uma adaptação do HITS original, para que
ele fosse independente dos termos de busca e também para garantir que os resultados
não dependam do valor inicial utilizado no método da potência.

As modificações no algoritmo foram:

\begin{itemize}
	\item Usar o grafo da web no lugar do grafo de vizinhança $N$.
	\item Utilizar novas matrizes no lugar das matrizes $L'L$ e $LL'$, a saber:\\
	$\xi L'L + (1 - \xi)/n \, ee'$ e $\xi LL' + (1 - \xi)/n \, ee'$ respectivamente,
	com $0 < \xi < 1$.\\
	Estas novas matrizes são irredutíveis, garantindo assim a unicidade dos vetores
	$x$ e $y$ pelo teorema de Perron-Frobenius.
\end{itemize}

Novamente usaremos o método da potência para calcular os vetores $x$ e $y$, cujo
pseudo-código é:

\texttt{
  \begin{algorithmic}
  \STATE $x^{(0)} \gets (1/n)e$
  \STATE $y^{(0)} \gets (1/n)e$
  \WHILE {$res_1 \geqslant \epsilon \, \OR \, res_2 \geqslant \epsilon$}
    \STATE $x^{(k)} \gets x^{(k-1)}L'$
    \STATE $x^{(k)} \gets x^{(k)}L$
    \STATE $y^{(k)} \gets y^{(k-1)}L$
    \STATE $y^{(k)} \gets y^{(k)}L'$
    \STATE $x^{(k)} \gets x^{(k)}/||x^{(k)}||_1$
    \STATE $y^{(k)} \gets y^{(k)}/||y^{(k)}||_1$
    \STATE $res_1 \gets ||x^{(k)} - x^{(k-1)}||_1$
    \STATE $res_2 \gets ||y^{(k)} - y^{(k-1)}||_1$
  \ENDWHILE
\end{algorithmic}
}

Note que com esta modificação, não é mais possível iterar apenas para calcular
$x$, conseguindo um $y$ no final. Foi necessário colocar o cálculo de $y$ para
dentro da parte iterativa do algoritmo.

Esta é uma desvantagem quanto ao método original, pois cada iteração do método
da potência agora é duas vezes mais custosa. No entanto, isso é compensado pelo
número menor de iterações que o HITS leva para convergir.
